# !/usr/bin/env python
# -*- coding:utf-8 -*-
# @FileName : HJ24.py
# @Time     : 2024/2/28 19:13
# @Author   : Robot-Zsj
"""
description: 

N位同学站成一排，音乐老师要求最少的同学出列，使得剩下的K位同学排成合唱队形。

设K位同学从左到右依次编号为1,2。。。，K，他们的身高分别为T1，T2，。。。，TK，

若存在i(1<=i<=K)使得T1<T2<...<Ti-1<Ti且Ti>Ti+1>...>TK，则称这K名同学排成了合唱队形。

通俗来说，能找到一个同学，他的两边的同学身高都依次严格降低的队形就是合唱队形。

123 124 125 123 121 是一个合唱队形
123 123 124 122 不是合唱队形，因为前两名同学身高相等，不符合要求
123 122 121 122 不是合唱队形，因为找不到一个同学，他的两侧同学身高递减。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

注意：不允许改变队列元素的先后顺序 且 不要求最高同学左右人数必须相等

输入描述：
用例两行数据，第一行是同学的总数N，第二行是N位同学的身高，以空格隔开

输出描述：
最少需要几位同学出列

示例：
输入：8
     186 186 150 200 160 130 197 200
输出：4

说明：186         200 160 130
         186 150             197 200
"""

"""
解析：

此题是最长递增子序列的变体，基本思想是对原序列从左到右和从右到左分别求出到每个元素的最长递增子序列的长度。

例如，原序列为长度为N的序列[8,20,12,15,10,9]，从左到右的到序列里每个元素的最长递增子序列为l1=[1,2,2,3,2,2]，

从左到右，也就是
8                0  1
8 20             1  2
8 20,8,12        2  2
8 12 15          3  3 
8 20, 12 15      4  2
8 20, 12 15      5  2
  
从右到左为l2=[1,4,3,3,2,1]，l1+l2=[2,6,5,6,4,3]。那么合唱队最长队伍是L=max(l1+l2)-1，
减1是因为计算l1和l2时重复计算了一次元素本身。因此最少出列人数为原序列长度N-L。

此题的关键在于求出l1，l2,。

可由动态规划求出，用dp[i]表示从左至右到原序列第i个元素的最长递增子序列的长度，从第i个元素往回遍历更新dp[i]的值。

由于每个元素都需要往回遍历一次，时间复杂度是O(n^2)。往回遍历如何更新dp[i]的值在其他题解已有很好的介绍，
这里主要写用二分法代替往回遍历的过程，时间复杂度为o(nlogn)

二分法的过程为：首先创建数组arr=[ele_1],ele_1是原序列第一个元素，然后从第二个元素开始从左至右遍历原序列

1. 如果ele_i>max(arr)，将ele_i加到arr最后
2. 如果ele_i<=max(arr),用二分法找到arr中第一个比ele_i大（或者相等）的元素并用ele_i替换

遍历完成后arr的长度即为最长递增子序列的长度(但arr不是最长递增子序列).
第二步替换是因为遍历到的元素可能会有比ele_i大但比替换元素小的元素

"""

import bisect


def inc_max(l):
    dp = [1] * len(l)
    arr = [l[0]]
    for i in range(1, len(l)):
        if l[i] > arr[-1]:
            arr.append(l[i])
            dp[i] = len(arr)
        else:
            pos = bisect.bisect_left(arr, l[i])
            arr[pos] = l[i]
            dp[i] = pos + 1
    return dp


while True:
    try:
        N = int(input())
        s = list(map(int, input().split()))
        left_s = inc_max(s)
        right_s = inc_max(s[::-1])[::-1]
        sum_s = [left_s[i] + right_s[i] - 1 for i in range(len(s))]
        print(str(N - max(sum_s)))
    except:
        break
